import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringJoiner;

public class 在O的时间内使用常数级空间复杂度对链表进行排序 {
    
    public static void main(String[] args) {

        ListNode rooNode = new ListNode(30);
        ListNode node1 = new ListNode(20);
        node1.next = new ListNode(40);
        rooNode.next = node1;

        ListNode result = sortList1 (rooNode);

        System.out.println(result.toString());

    }

    public static ListNode sortList1 (ListNode head) {
        // write code here
        if (head == null || head.next == null) return head;
        LinkedList<ListNode> queue = new LinkedList<ListNode>();
        ListNode cur = head;
        while (cur != null) {
            queue.offer(cur);
            cur = cur.next;
        }

        queue.sort((a, b) -> a.val - b.val);

        ListNode dummy = new ListNode(0);
        cur = dummy;
        while (!queue.isEmpty()) {
            cur.next = queue.poll();
            cur = cur.next;
        }
        cur.next = null;
        return dummy.next;
    }

    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    private static ListNode sortList (ListNode head) {
        // write code here

        if (head == null || head.next == null) {
            return head;
        }
        ListNode mid = findMid(head);
        ListNode left = sortList(head);
        ListNode right = sortList(mid);
        return merge(left, right);
    }

    public static ListNode findMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast!= null && fast.next!= null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        slow.next = null;
        return mid;
    }

    public static ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (l1!= null && l2!= null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        if (l1!= null) {
            curr.next = l1;
        }
        if (l2!= null) {
            curr.next = l2;
        }
        return dummy.next;
    }



    private static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }

        public String toString(){

            StringJoiner stringJoiner = new StringJoiner(", ");
            stringJoiner.add(val+"");

            ListNode curNode = this;

            while (null!=curNode.next) {

                stringJoiner.add(curNode.next.val+"");

                curNode = curNode.next;
            }

            return stringJoiner.toString();


        }
    }
}
